Implementing Bucket Sort Algorithm in C++
Bucket sort is a non-comparison sorting algorithm that sorts elements by distributing them into multiple "buckets", sorting each bucket individually, and then merging the sorted buckets. The core is to reasonably partition the buckets so that each bucket contains a small number of elements, thereby reducing the sorting cost. Taking floating-point numbers in the range [0,1) as an example, the algorithm steps are as follows: 1. Create n empty buckets (where n is the length of the array); 2. Assign each element x to the corresponding bucket using the bucket index calculated as the integer part of x * n; 3. Sort each bucket using std::sort; 4. Merge all elements from the buckets. In the C++ implementation, the `bucketSort` function creates n buckets using a vector of vectors of doubles, distributes elements into the buckets through traversal, sorts each bucket, and then merges the results. Testing verifies the correctness of the algorithm. Complexity analysis: The average time complexity is O(n) (when elements are uniformly distributed), and the worst-case time complexity is O(n log n) (when all elements are placed in the same bucket). The space complexity is O(n). It is suitable for numerical data with uniformly distributed values and a clear range; performance degrades when data distribution is uneven. This algorithm is efficient when the data distribution is reasonable, especially suitable for sorting interval data in statistical analysis.
Read MoreImplementing the Counting Sort Algorithm in C++
**Counting Sort** is a non-comparison sorting algorithm. Its core idea is to construct a sorted array by counting the occurrences of elements, making it suitable for scenarios where the range of integers is not large (e.g., student scores, ages). **Basic Idea**: Taking the array `[4, 2, 2, 8, 3, 3, 1]` as an example, the steps are: 1. Determine the maximum value (8) and create a count array `count` to statistics the occurrences of each element (e.g., `count[2] = 2`); 2. Insert elements into the result array in the order of the count array to obtain the sorted result `[1, 2, 2, 3, 3, 4, 8]`. **Implementation Key Points**: In C++ code, first find the maximum value, count the occurrences, construct the result array, and copy it back to the original array. Key steps include initializing the count array, counting occurrences, and filling the result array according to the counts. **Complexity**: Time complexity is O(n + k) (where n is the array length and k is the data range), and space complexity is O(k). **Applicable Scenarios**: Non-negative integers with a small range, requiring efficient sorting; negative numbers can be handled by offset conversion (e.g., adding the minimum value). Counting Sort achieves linear-time sorting through the "counting-construction" logic and is ideal for processing small-range integers.
Read MoreImplementing the Radix Sort Algorithm with Python
Radix sort is a non-comparative integer sorting algorithm. Its core idea is to distribute elements into buckets and collect them by each digit (from the least significant to the most significant). The basic steps are as follows: first, determine the number of digits of the maximum number in the array. Then, from the least significant digit to the most significant digit, perform "bucket distribution" (10 buckets for digits 0-9) and "collection" operations for each digit. Elements with the same current digit are placed into the same bucket, and the array is updated by collecting them in bucket order until all digits are processed. In Python, this is implemented by looping through the digits, calculating the current digit to distribute into buckets, and then collecting. The time complexity is O(d×(n+k)) (where d is the number of digits of the maximum number, n is the array length, and k=10), and the space complexity is O(n+k). It is suitable for integer arrays with few digits. When handling negative numbers, they can first be converted to positive numbers for sorting and then their signs can be restored.
Read MoreImplementing the Counting Sort Algorithm in Python
Counting sort is an efficient non-comparison sorting algorithm suitable for integers with a small value range. Its time complexity is O(n + k), where n is the number of elements and k is the data range. Core steps: 1. Determine the data range (find min and max); 2. Construct a counting array to count the occurrences of each element; 3. Output the elements of the counting array in order (outputting the number of times corresponding to the count). It is stable (relative order of duplicate elements remains unchanged), and memory usage depends on the data range. It is suitable for integer data with many duplicates or a small range (e.g., exam scores). The Python implementation completes sorting through boundary handling, counting occurrences, etc. Test cases verify its applicability to arrays with duplicate elements and negative numbers.
Read MoreImplementing Radix Sort Algorithm in Java
Radix sort is a non-comparison integer sorting algorithm that processes digits from the least significant to the most significant. It distributes each number into "buckets" based on the current digit, then collects them back into the original array in bucket order, repeating until all digits are processed. It is suitable for integers with few digits and has high efficiency. The basic idea is "distribute-collect-repeat": distribute numbers into corresponding buckets by the current digit (units, tens, etc.), collect them back into the array in bucket order, and repeat for all digits. Taking the array [5, 3, 8, 12, 23, 100] as an example, it is sorted after three rounds of processing: units, tens, and hundreds. In Java code, the maximum number determines the highest digit, and `(num / radix) % 10` is used to get the current digit. ArrayLists are used as buckets to implement distribution and collection. The time complexity is O(d(n+k)) (where d is the number of digits of the maximum number and k=10), and the space complexity is O(n+k). This algorithm is stable and suitable for integer sorting. Negative numbers can be separated into positive and negative groups, sorted separately, and then merged.
Read MoreImplementing Bucket Sort Algorithm in Java
Bucket sort is a non-comparison-based sorting algorithm. Its core idea is to distribute data into several "buckets", sort each bucket locally, and then merge the sorted buckets. It is suitable for scenarios where data is uniformly distributed and the range is not large (e.g., integers with a controllable range). The steps are: determine the number and range of buckets (e.g., for integers in the range 0 to max, the number of buckets is max+1), create corresponding bucket containers, traverse the elements to distribute them into the appropriate buckets, sort each bucket internally (e.g., using insertion sort or built-in methods), and finally merge the elements in the order of the buckets. The time complexity is ideally O(n), and the space complexity is O(n). Its advantages include high efficiency when data is uniformly distributed, while its disadvantages are space waste when the data range is large and efficiency degradation when the data distribution is uneven.
Read More